package com.wxg.algorithm.chapter03.comparable;

import com.wxg.algorithm.chapter02.comparable.InsertionSortV2;
import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

public class MergeSortV2<T extends Comparable> implements ISort<T> {

    private MergeSort ms;

    private InsertionSortV2 insertionSortV2;

    public MergeSortV2(){
        ms = new MergeSort();
        insertionSortV2 = new InsertionSortV2<T>();
    }

    @Override
    public void sort(T[] arr) {

        recursionMergeSort(arr, 0, arr.length-1);
    }

    /**
     * 递归: 对 arr[l...r] 的范围进行排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private void recursionMergeSort(T[] arr, int l, int r){

        // 递归到底的情况
//        if ( l >= r ){
//            return;
//        }

        // 优化, 当元素数量较少时,切换为使用"插入排序"
        if(r - l <= 15){
            insertionSortV2.sort(arr, l, r);
            return;
        }


        // 当 l 和 r 都非常大时(l+r)可能造成溢出
        int mid = (l + r)/2;

        recursionMergeSort(arr, l, mid);
        recursionMergeSort(arr, mid+1, r);

        // 优化
        if(arr[mid].compareTo(arr[mid+1]) > 0){
            merge(arr, l, mid, r);
        }

    }

    /**
     * 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    protected void merge(T[] arr, int l, int mid, int r) {
        ms.merge(arr, l, mid, r);
    }

    public static void main(String[] args) {
        MergeSortV2<Integer> ms = new MergeSortV2<>();
        InsertionSortV2<Integer> is = new InsertionSortV2<>();

        int n = 10000;
        Integer[] intArr01 = SortTestHelper.generateRandomArray(n, 0, n);
        Integer[] intArr02 = SortTestHelper.copyIntArray(intArr01);

        SortTestHelper.testSort(ms, intArr01);
        SortTestHelper.testSort(is, intArr02);

        // 对近乎有序的数组的排序
        System.out.println("=== 对近乎有序的数组的排序 ===");

        Integer[] intArr03 = SortTestHelper.generateNearlyOrderedArray(n, 10);
        Integer[] intArr04 = SortTestHelper.copyIntArray(intArr03);
        SortTestHelper.testSort(ms, intArr03);
        SortTestHelper.testSort(is, intArr04);
    }

}
